package com.ayuer.chapter06;

import java.util.LinkedList;

public class TreeTraversal02 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void preOrder(TreeNode root) {
        /**
         *       6
         *      / \
         *     7   5
         *        / \
         *       4   3
         *      / \
         *     2   1
         * 前 6->7->5->4->2->1->3
         * 中 7->6->2->4->1->5->3
         * 后 7->2->1->4->3->5->6
         */
        if (root == null) {
            return;
        }

        TreeNode curr = root;
        //记录来时的路
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print(curr.val + "->");
                stack.push(curr);
                curr = curr.left;
            } else {
                //栈不为空
                TreeNode pop = stack.pop();
//                System.out.print("回：" + pop.val + " ");
                //处理right节点
                curr = pop.right;
            }

        }
    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode curr = root;
        //记录来时的路
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
//                System.out.print(curr.val + "->");
                stack.push(curr);
                curr = curr.left;
            } else {
                //栈不为空
                TreeNode pop = stack.pop();
                System.out.print(pop.val + "->");
                //处理right节点
                curr = pop.right;
            }

        }
    }

    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode curr = root;
        //最近弹栈的节点
        TreeNode pop = null;
        //记录来时的路
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                //栈不为空
                //栈顶就是需要回溯的元素
                TreeNode peek = stack.peek();
                if (peek.right == null || pop == peek.right) {
                    pop = stack.pop();
                    //处理right节点
                    System.out.print(pop.val + "->");
                } else {
                    curr = peek.right;
                }
            }

        }
    }


    public static void main(String[] args) {
        /**
         *       6
         *      / \
         *     7   5
         *        / \
         *       4   3
         *      / \
         *     2   1
         * 前 6->7->5->4->2->1->3
         * 中 7->6->2->4->1->5->3
         * 后 7->2->1->4->3->5->6
         */

        TreeNode t1 = new TreeNode(1, null, null);
        TreeNode t2 = new TreeNode(2, null, null);
        TreeNode t3 = new TreeNode(3, null, null);
        TreeNode t4 = new TreeNode(4, t2, t1);
        TreeNode t5 = new TreeNode(5, t4, t3);
        TreeNode t6 = new TreeNode(7, null, null);
        TreeNode root = new TreeNode(6, t6, t5);
        TreeTraversal02.preOrder(root);
        System.out.println();
        TreeTraversal02.inOrder(root);
        System.out.println();
        TreeTraversal02.postOrder(root);
    }


}
